import java.util.*;

public class Solution42 {
    public int trap(int[] height) {
        TreeMap<Integer, Integer> left = new TreeMap<>(), right = new TreeMap<>();
        for (int i = 0; i < height.length; i++) {
            Integer tmpHeight = height[i];
            right.put(tmpHeight, right.getOrDefault(tmpHeight, 0) + 1);
        }
        int res = 0;
        for (int i = 0; i < height.length; i++) {
            Integer tmpHeight = height[i];
            right.put(tmpHeight, right.get(tmpHeight) - 1);
            if(right.get(tmpHeight) == 0){
                right.remove(tmpHeight);
            }
            if(!left.isEmpty() && !right.isEmpty()){
                int sideHeight = Math.min(left.lastKey(), right.lastKey());
                if(tmpHeight < sideHeight){
                    res += sideHeight - tmpHeight;
                }
            }
            left.put(tmpHeight, left.getOrDefault(tmpHeight, 0) + 1);
        }
        return res;
    }
}
